package algorithm;

import java.util.Random;

public class LCS_subsuquence {
	public static void main(String[] args) {
		int stringLongth_1 = 10;
		int stringLongth_2 = 15;
		
		String x = getRandomString(stringLongth_1);
		String y = getRandomString(stringLongth_2);
		
		Long start = System.currentTimeMillis();
		int[][] opt = new int[stringLongth_1 + 1][stringLongth_2 + 1];
		for (int i = stringLongth_1 - 1; i >= 0 ; i--) {
			for (int j = stringLongth_2 - 1; j >= 0; j--) {
				if(x.charAt(i) == y.charAt(j)){
					opt[i][j] = opt[i + 1][j + 1] + 1;
				}else{
					opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
				}
			}
		}
		int i = 0;
		int j = 0;
		System.out.println("x: " + x);
		System.out.println("y: " + y);
		while(i < stringLongth_1 && j < stringLongth_2){
			if(x.charAt(i) == y.charAt(j)){
				System.out.print(x.charAt(i));
				i++;
				j++;
			}else if(opt[i + 1][j] >= opt[i][j + 1]){
				i++;
			}else{
				j++;
			}
		}
		System.out.println();
		long end = System.currentTimeMillis();
		
		for (int k = 0; k < opt.length; k++) {
			for (int k2 = 0; k2 < opt[i].length; k2++) {
				System.out.print(opt[k][k2] + " ");
			}
			System.out.println();
		}
		System.out.println("time: " + (end - start));
	}
	
	public static String getRandomString(int length){
		//abcdefghijklmnopqrstuvwxyz
		StringBuffer builder = new StringBuffer("abcdefgh");
		StringBuffer sb = new StringBuffer();
		Random random = new Random();
		int range = builder.length();
		for (int i = 0; i < length; i++) {
			sb.append(builder.charAt(random.nextInt(range)));
		}
		return sb.toString();
	}
}
